package com.java.comprehensive.arithmetic.leecode.tags.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: comprehensive-service
 * @description: 四数之和
 * @author: 窦绍飞
 * @create: 2021-12-09 10:19
 **/
public class LeetCode_18 {

	public static List<List<Integer>> fourSum(int[] nums, int target) {
		Arrays.sort(nums);

		List<List<Integer>> listList = new ArrayList<>();
		if (nums == null || nums.length < 4) {
			return listList;
		}

		int n = nums.length;
		for (int i = 0; i < n - 3; i++) {
			if (i > 0 && nums[i] == nums[i - 1]) {
				continue;
			}
			if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
				break;
			}
			if ((long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) {
				continue;
			}

			for (int j = i + 1; j < n - 2; j++) {
				if (j > i + 1 && nums[j] == nums[j - 1]) {
					continue;
				}
				if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
					break;
				}
				if ((long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) {
					continue;
				}

				int l = i + 1, r = n - 1;
				while (l < r) {
					int sum = nums[i] + nums[j] + nums[l] + nums[r];
					if (sum == target) {
						listList.add(Arrays.asList(i, j, l, r));
						while (l < r && nums[l] == nums[l + 1]) {
							l++;
						}
						l++;
						while (l < r && nums[r] == nums[r - 1]) {
							r--;
						}
						r--;
					} else if (sum < target) {
						l++;
					} else {
						r--;
					}
				}
			}
		}

		return listList;
	}

	public static List<List<Integer>> fourSumTwo(int[] nums, int target) {

		List<List<Integer>> result = new ArrayList<>();

		Arrays.sort(nums);
		int n = nums.length;
		for (int i = 0; i < n; i++) {
			if (i > 0 && nums[i] == nums[i - 1]) continue;
			for (int j = i + 1; j < n; j++) {
				if (j > i + 1 && nums[j] == nums[j - 1]) continue;
				int l = j + 1, r = n - 1;
				long sum = (long) target - ((long) nums[i] + (long) nums[j]);
				while (l < r) {
					if (sum == nums[l] + nums[r]) {
						result.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
						while (l < r && nums[l] == nums[l + 1]) l++;
						while (l < r && nums[r] == nums[r - 1]) r--;
						l++;
						r--;
					} else {
						if (sum > nums[l] + nums[r]) {
							l++;
						}
						if (sum < nums[l] + nums[r]) {
							r--;
						}
					}
				}
			}
		}
		return result;
	}

	public static void main(String[] args) {
		int[] nums = {1000000000, 1000000000, 1000000000, 1000000000};
		int target = -294967296;
		System.out.println(fourSumTwo(nums, target));
	}
}
